package Leetcode.Dichotomy;

/**
 * @Author: kirito
 * @Date: 2024/4/10 12:59
 * @Description:
 * 乘法表中第k小的数
 * 困难
 * 相关标签
 * 相关企业
 * 几乎每一个人都用 乘法表。但是你能在乘法表中快速找到第 k 小的数字吗？
 *
 * 乘法表是大小为 m x n 的一个整数矩阵，其中 mat[i][j] == i * j（下标从 1 开始）。
 *
 * 给你三个整数 m、n 和 k，请你在大小为 m x n 的乘法表中，找出并返回第 k 小的数字。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：m = 3, n = 3, k = 5
 * 输出：3
 * 解释：第 5 小的数字是 3 。
 * 示例 2：
 *
 *
 * 输入：m = 2, n = 3, k = 6
 * 输出：6
 * 解释：第 6 小的数字是 6 。
 *
 *
 * 提示：
 *
 * 1 <= m, n <= 3 * 104
 * 1 <= k <= m * n
 */

public class findKthNumber {
    public static void main(String[] args) {
        int m = 2, n = 3, k = 6;
        System.out.println(findKthNumber(m, n, k));
    }
    public static int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (!check(m, n, mid, k)) {
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return left;
    }

    private static boolean check(int m, int n, int mid, int k) {
        int num = 0;
        int i = m, j = 1;
        while (i >= 1 && j <= n) {
            if (i * j <= mid) {
                num += i;
                j++;
            }else{
                i--;
            }
        }
        return num >= k;
    }
}
